package com.xzz.listnode;

/**
 * @author: hhz
 * @create: 2021-12-23 13:47
 **/
public class IsPalindrome {
    public static void main(String[] args) {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
//        ListNode node3 = new ListNode(2);
//        ListNode node4 = new ListNode(1);
        node1.next = node2;
//        node2.next = node3;
//        node3.next = node4;
        boolean palindrome = isPalindrome(node1);
        System.out.println();
    }

    static ListNode left;

    public static boolean isPalindrome(ListNode head) {
//        left = head;
//        return traverse(head);
        ListNode slow = head;
        ListNode fast = head;
        while (fast!=null && fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;
        }
        //奇数 慢指针需要再走一步
        if(fast!=null){
            slow = slow.next;
        }

        //翻转慢指针后的节点，返回的头节点 就是右指针
        ListNode right = reverse(slow);
        ListNode leftNode = head;
        while(right!=null){
            if(leftNode.val!= right.val){
                return false;
            }
            right = right.next;
            leftNode = leftNode.next;
        }
        return true;

    }

    //双指针 头尾向中解法 O(N)
    public static boolean traverse(ListNode right) {
        if (right == null) {
            return true;
        }
        boolean traverse = traverse(right.next);
        traverse = (traverse && left.val == right.val);
        left = left.next;
        return traverse;
    }

    //从头翻转链表，迭代
    public static ListNode reverse(ListNode node) {
        ListNode cur = node;
        ListNode pre = null;
        ListNode next = node;
        while(cur!=null){
            next = cur.next;
            cur.next = pre;
            //注意顺序
            pre = cur;
            cur = next;
        }
        return pre;
    }
}
